max_size = 100


class SString:
    def __init__(self):
        # 初始化一个空的串
        self.length = 0  # 串当前长度
        self.ch = [None] * max_size  # 最大长度为max_size的空间

    def str_assign(self, s):
        # 把串的值赋为s
        n = len(s)  # 求串s的长度
        if n > max_size - 1:  # 此处为max_size - 1因为0号单元弃用
            raise Exception('空间已满')
        else:
            self.length = 0  # 把串置为空
            while self.length < n:
                self.length += 1
                self.ch[self.length] = s[self.length - 1]
        return self

    def index_bf(self, s, t, pos):
        # 返回模式t在主串s中第pos个字符之后第一次出现的位置。若不存在，则返
        # 回值为0
        # 其中，t非空，1≤pos≤s.length
        i = pos
        j = 1  # 初始化
        while i <= s.length and j <= t.length:  # 两串均未比较到串尾
            if s.ch[i] == t.ch[j]:
                i += 1
                j += 1
            else:
                i = i - j + 1 + 1  # 回溯，这里加1是因为前面代码中串实际存储从1号单元开始，索引需要对应调整
                j = 1
        if j > t.length:
            return i - t.length  # 匹配成功
        else:
            return 0  # 匹配失败


if __name__ == '__main__':
    s, t = SString(), SString()
    ss = '123'
    tt = '23'
    pos = 1
    # 正确调用方式，通过s实例调用index_bf方法，传入相应的主串、子串以及查找位置参数
    result = s.index_bf(s.str_assign(ss), t.str_assign(tt), pos)
    print('主串{0}和字串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), result)

    ss = '123210'
    tt = '21'
    pos = 2
    result = s.index_bf(s.str_assign(ss), t.str_assign(tt), pos)
    print('主串{0}和字串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), result)

    ss = '111111111'
    tt = '111'
    pos = 8
    result = s.index_bf(s.str_assign(ss), t.str_assign(tt), pos)
    print('主串{0}和字串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), result)

    max_size = 100







    class SString:
        def __init__(self):
            # 初始化一个空的串
            self.length = 0  # 串当前长度
            self.ch = [None] * max_size  # 最大长度为max_size的空间

        def str_assign(self, s):
            # 把串的值赋为s
            n = len(s)  # 求串s的长度
            if n > max_size - 1:  # 此处为max_size - 1因为0号单元弃用
                raise Exception('空间已满')
            else:
                self.length = 0  # 把串置为空
                while self.length < n:
                    self.length += 1
                    self.ch[self.length] = s[self.length - 1]
            return self

        def index_bf(self, s, t, pos):
            i = pos
            j = 1  # 初始化
            while i <= s.length and j <= t.length:  # 两串均未比较到串尾
                if s.ch[i] == t.ch[j]:
                    i += 1
                    j += 1
                else:
                    i = i - j + 1 + 1  # 回溯，这里加1是因为前面代码中串实际存储从1号单元开始，索引需要对应调整
                    j = 1
            if j > t.length:
                return i - t.length  # 匹配成功
            else:
                return 0  # 匹配失败


    def virus_detection(v, p):
        # 利用BF算法实现病毒检测
        virus = SString()
        person = SString()
        virus.str_assign(v)  # 读取病毒DNA序列
        person.str_assign(p)  # 读取人的DNA序列
        flag = 0  # 用来标识是否匹配，初始为0，匹配后为非0
        m = virus.length  # 病毒DNA序列的长度是m
        for i in virus.ch[1: m + 1]:  # 病毒序列扩展到原来的2倍
            virus.length += 1
            virus.ch[virus.length] = i
        j = 1
        while j <= m:  # 依次取得每个长度为m的病毒DNA环状字符串temp
            temp = SString()
            temp.str_assign(virus.ch[j:j + m])
            flag = person.index_bf(person, temp, 1)  # 此处修改，传入person对象自身作为主串对象参数
            if flag:  # 匹配即可退出循环
                break
            j += 1
        if flag:
            print('YES')
        else:
            print('NO')


    if __name__ == '__main__':
        v, p = 'baa', 'bbaabbba'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'baa', 'aaabbbba'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'aabb', 'abceaabb'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'aabb', 'abaabcea'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'abcd', 'cdabbbab'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'abcd', 'cabbbbab'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'abcde', 'bcdedbda'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'acc', 'bdebdcda'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'cde', 'cdcdcdec'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)
        v, p = 'cced', 'cdccdcce'
        print('{v} {p}的检测结果为：'.format(v=v, p=p), end='')
        virus_detection(v, p)